package 动态规划专项训练.动态规划训练1;

/**剑指OfferII091.粉刷房子
 * 序列型动态规划
 * @author zx
 * @create 2022-03-30 17:33
 */
public class Num256 {
    public int minCost(int[][] costs) {
        int n = costs.length;
        if(n == 0){
            return 0;
        }
        int[][] f = new int[n + 1][3];//n个房子,开n + 1个数组长度
        //初始化条件
        f[0][0] = f[0][1] = f[0][2] = 0;
        for(int i = 1;i <= n;i++){
            //j是房子(i - 1)的颜色
            for(int j = 0;j < 3;j++){
                f[i][j] = Integer.MAX_VALUE;
                //k是房子(i - 2)的颜色
                for(int k = 0;k < 3;k++){
                    //不能撞色
                    if(j == k){
                        continue;
                    }
                    if(f[i - 1][k] + costs[i - 1][j] < f[i][j]){
                        f[i][j] = f[i - 1][k] + costs[i - 1][j];
                    }
                }
            }
        }
        int res = f[n][0];
        if(f[n][1] < res){
            res = f[n][1];
        }
        if(f[n][2] < res){
            res = f[n][2];
        }
        return res;
    }
}
